class Solution:
    def maxProfit(self, k: int, prices) -> int:
        if not prices:
            return 0
        n=len(prices)
        k=min(k,n//2)
        buy=[[0]*(k+1) for _ in range(n)]
        sell=[[0]*(k+1) for _ in range(n)]
        for i in range(1,k+1):
            buy[0][i]=float("-inf")
            sell[0][i]=float("-inf")
        buy[0][0]=-prices[0]
        for i in range(1,n):
            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i])
            for j in range(1, (k+1)):
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i])
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]) 
        print(buy)
        print(sell)
        return max(sell[n-1])

s=Solution()
s.maxProfit(2,[3,2,6,5,0,3])
